One of the most well-known nonblocking multi-stage switching network designs is due to Clos (C. Clos, "A study of nonblocking switching networks," The Bell System Technical Journal, vol. 41, pp. 1201-1247, 1962). The so-called Clos network provides strictly nonblocking connecting capability for permutation assignments between input ports and output ports in which each input port can be connected to at most one output port in a one-to-one fashion. For a v(m,n,r) network, Clos showed that if m.gtoreq.2n-1, the network was strictly nonblocking; and for a v(m,n.sub.1,r.sub.1,n.sub.2,r.sub.2) network, if m.gtoreq.n.sub.1 +n.sub.2 -1, the network was again strictly nonblocking. The Clos network structure demonstrated that strictly nonblocking multi-stage switching networks could be designed at a considerable savings in switching costs as compared with the obvious alternative of using a large single-stage switch with a crosspoint switching element between each input port and output port. Cantor (D. Cantor, "On nonblocking switching networks," Networks, vol. 2, pp. 367-377, 1972) later improved upon the Clos design with an alternative multi-stage structure that could provide strictly nonblocking connecting capability for permutation assignments with asymptotically fewer crosspoints.
It is not surprising that nonblocking networks designed for permutation assignments are not in general nonblocking for broadcast assignments, and, indeed, do not even necessarily satisfy all broadcast assignments (G. M. Masson, "Upper bounds on fanout in connection networks," IEEE Trans Circuits and Systems (Special Issue on Large-Scale Systems), vol. CT-20, pp. 222-230, 1973). Masson (G. M. Masson and B. W. Jordan, "Realization of a class of multiple connection assignments with multi-stage connection networks," Proceedings of the Fifth Annual Princeton Conference on Information Sciences and Systems, pp. 316-321, 1971; G. M. Masson and B. W. Jordan, "Generalized multi-stage connection networks," Networks, vol. 2, pp. 191-209, 1972) first gave designs for strictly nonblocking and rearrangeable multi-stage switching networks for broadcast assignments. For the case of a three-stage v(m,n,r) network, it was shown for broadcast assignments that if m.gtoreq.n(r+1)-1, the network was strictly nonblocking, and if m.gtoreq.nr, the network was rearrangeable. Hwang (F. K. Hwang, "Rearrangeability of multiconnection three-stage networks," Networks, vol. 2, pp. 301-306, 1972) later pointed out that if, for some reason, the middle stage switch modules did not have broadcast capability so that all connection path fanout must take place in the input and output stage switch modules, then Masson's condition on the number of middle stage switch modules for rearrangeable connection capability was necessary and sufficient.
Hwang and Jajszczyk (F. K. Hwang, "Three-stage multi-connection networks which are nonblocking in the wide sense." Bell System Technical Journal, vol. 58, pp. 1283-1287, 1979; A. Jajszczyk, "Comments on: Three-stage multi-connection networks which are nonblocking in the wide sense," Bell System Technical Journal, vol. 62, pp. 2113-2114, 1983; F. K. Hwang and A. Jajszczyk, "On nonblocking multiconnection networks," IEEE Trans. Communications, vol. COM-34, pp. 1038-1041, 1986) have given a set of design conditions for nonblocking multi-stage multi-connection switching networks. A multi-connection is a generalization of a broadcast connection in the sense that input sets are connected to output sets.
Masson (G. M. Masson, "Binomial switching networks for concentration and distribution," IEEE Trans. Communications, vol. Com-25, pp. 873-884, 1977) has also shown a two-stage design of a rearrangeable broadcast switching network which cascades sparse crossbar switching structures that function as concentrators (G. M. Masson, "Lower Bounds on crosspoints in concentrators," IEEE Trans Computers, vol. C-31, pp. 1173-1179, 1982) with broadcast switching modules. Later, Kufta and Vacroux (R. W. Kudta and A. G. Vacroux, "Multiple stage networks with fanout capabilities," Proceedings Computer Networking Symp., Silver Spring, Md., pp. 89-96, 1983) and then Richards and Hwang (G. W. Richards and F. K. Hwang, "A two-stage rearrangeable broadcast switching network," IEEE Trans. Communications, vol. COM-33, pp. 1025-1034, 1985; G. W. Richards and F. K. Hwang, "A two-stage rearrangeable broadcast switching network," Proceedings of the 11th International Teletraffic Congress, pp. 1083-1087, Kyoto, Japan, September 1985) used Masson's two-stage concept as the basis of re-configured and extended--but nevertheless fundamentally similar--rearrangeable broadcast network designs. It should be mentioned that although the reconfigured form of Masson's initial two-stage design concept was patented by Richards (G. W. Richards, "Rearrangeable multiconnection switching networks," U.S. Pat. No. 4,566,007 Jan. 21, 1986), the fundamental design concept had been previously known (G. M. Masson, Report on fan-out switching networks, presented to P. Fire and H. Graves, GTE Sylvania, and T. Dixon, Department of Defense, Mountain View, Calif., 1973).
Other techniques of cascading networks of various types to achieve broadcasting capability have been considered. Lea (Chin-Tau Lea, "A new broadcast switching network," IEEE Trans . Communications, vol. COM-36, pp. 1128-1137, 1988) has studied cascading a spreading (or fanout) multi-stage network with a permutation network for the design of rearrangeable broadcast networks. Turner (J. S Turner, "Practical wide-sense nonblocking generalized connectors," Washington University Computer Science Research Report-88-29, 1988) has considered the cascading of Cantor and Clos networks to achieve nonblocking broadcast connection capability. Finally, Kumar (M. Kumar, "Supporting broadcast connections in Benes networks" IBM Research Report RC-14063, 1988) has studied a five-stage construction based on the overlapping of two three-stage networks as a rearrangeable broadcast network design.
Dolev, Dwork, Pippenger, and Wigderson (D. Dolev, C. Dwork, N. Pippenger, and A. Wedgerson, "Superconcentrators, generalizers and generalized connectors with limited depth," Proc. of the 15th Annual ACM Symposium on Theory of Computing, pp. 42-51, 1983) have given minimum possible upper bounds on the number of crosspoints required for k-stage rearrangeable broadcast networks. Subsequently, Feldman, Friedman, and Pippenger (P. Feldman, J. Friedman, and N. Pippenger, "Wide-sense nonblocking networks," SIAM Journal of Discrete Mathematics, vol. 1, No. 2, pp. 158-173, May 1988) showed improved upper bounds for k-stage nonblocking broadcast networks. But neither explicit constructions nor efficient control algorithms for networks satisfying these bounds are known. However, Dolev, Dwork, Pippenger, and Wigderson (D. Dolev, C. Dwork, N. Pippenger, and A. Wedgerson, "Superconcentrators, generalizers and generalized connectors with limited depth," Proc of the 15th Annual ACM Symposium on Theory of Computing, pp. 42-51, 1983) did offer a construction for a (3k-2) stage rearrangeable broadcast network (where k.gtoreq.1) and Feldman, Friedman, and Pippenger (P. Feldman, J. Friedman, and N. Pippenger, "Wide-sense nonblocking networks," SIAM Journal of Discrete Mathematics, vol. 1, No. 2, pp. 158-173, May 1988) gave constructions for two-stage and three-stage nonblocking broadcast networks. Finally, by means of an application of a hypergraph-hypercolouring theorem, Kirkpatrick, Klawe, and Pippenger (D. G. Kirkpatrick, M. Klawe and N. Pippenger, "Some graph-colouring theorems with applications to generalized connection networks," SIAM Journal of Alg. Disc, Math., vol. 6, No. 4, pp. 576-582, October 1985) gave constructive designs for multi-stage rearrangeable broadcast networks.
The present invention is concerned with the design of broadcast networks to provide so-called nonblocking connecting capability in multi-stage switching networks. In these nonblocking broadcast networks, any broadcast connection request from a network input port to a set of network output ports can be realized without any disturbance (that is, rearrangement) of other existing broadcast connections with the restriction that at no time is any output port connected to more than one input port. Additionally, a network output port that is connected to a network input port in some broadcast connection, can upon disconnection from that network input port be included in future broadcast connection requests made by network input ports. The present invention also involves a linear algorithm for satisfying new broadcast connection requests in the network. These nonblocking broadcast network designs are an improvement in terms of required switching elements and network control complexity over other previously known designs, even including some rearrangeable broadcast network designs.